package id.ac.itb.BubbleBlast2Solver;

import id.ac.itb.GenericSolver.AbstractState;
import id.ac.itb.GenericSolver.AbstractStep;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Direction of Bubble Shot
 * @author Edward Samuel
 */
enum Direction {
	Up, Down, Left, Right
}

/**
 * Bubble Shot
 * @author Edward Samuel
 */
class Shot {
	/**
	 * Row (start at 0)
	 */
	public int row;
	/**
	 * Column (start at 0)
	 */
	public int col;
	/**
	 * Direction of Bubble Shot
	 */
	public Direction direction;

	/**
	 * Create new Bubble Shot (based on row, column, and direction) 
	 * @param row Row (start at 0)
	 * @param col Column (start at 0)
	 * @param direction Direction of Bubble Shot
	 */
	public Shot(int row, int col, Direction direction) {
		this.row = row;
		this.col = col;
		this.direction = direction;
	}

	/**
	 * Get direction of Bubble Shot is in vertical direction (up or down) 
	 * @return true, if the direction is up or down
	 */
	public boolean isVerticalShot() {
		return direction == Direction.Up || direction == Direction.Down;
	}
	
	/**
	 * Get direction of Bubble Shot is in horizontal direction (left or right) 
	 * @return true, if the direction is left or right
	 */
	public boolean isHorizontalShot() {
		return direction == Direction.Left || direction == Direction.Right;
	}

	/**
	 * Move one step of the Bubble Shot based on the direction 
	 * @return true, if the position of Bubble Shot is inside the Board 
	 */
	public boolean move() {
		switch (direction) {
		case Up:
			row--;
			break;
		case Down:
			row++;
			break;
		case Left:
			col--;
			break;
		case Right:
			col++;
			break;
		}

		return isInsideBoard();
	}

	/**
	 * Determines the Bubble Shot is inside the Board
	 * @return
	 */
	public boolean isInsideBoard() {
		return (row >= 0 && row < Board.NROW && col >= 0 && col < Board.NCOL);
	}
}

/**
 * Bubble Blast 2 Game Board (state of game)
 * @author Edward Samuel
 */
public class Board extends AbstractState {
	/**
	 * Number of rows
	 */
	public static final int NROW = 6;
	/**
	 * Number of columns
	 */
	public static final int NCOL = 5;

	/**
	 * Board data (contain information of bubbles state)
	 * Possible value of each element:
	 * -1 = No bubble
	 *  0 = Bubble burst
	 *  1 = Red Bubble
	 *  2 = Green Bubble
	 *  3 = Yellow Bubble
	 *  4 = Blue Bubble
	 */
	private int data[][];

	/**
	 * Create empty board 
	 */
	private Board() {
		super();
	}

	/**
	 * Copy exist board to a new one
	 * @param board Existed board
	 */
	public Board(Board board) {
		data = new int[NROW][];
		for (int m = 0; m < NROW; m++) {
			data[m] = new int[NCOL];
			for (int n = 0; n < NCOL; n++) {
				data[m][n] = board.data[m][n];
			}
		}
	}

	/**
	 * Create new board based on InputStream
	 * Possible data:
	 * _ = Empty
	 * R = Red
	 * G = Green
	 * Y = Yellow
	 * B = Blue
	 * 
	 * InputStream example:
	 * 
	 * __G_R
	 * YRBBY
	 * BGB_R
	 * BRRBG
	 * GRGBB
	 * GRGGR
	 * 
	 * 
	 * It makes a new board:
	 * 
	 * | . | . | G | . | R |
	 * | Y | R | B | B | Y |
	 * | B | G | B | . | R |
	 * | B | R | R | B | G |
	 * | G | R | G | B | B |
	 * | G | R | G | G | R |
	 * 
	 * @param istream Input stream, that contain board data information
	 * @return a new Board based on InputStream data
	 */
	public static Board createBoard(InputStream istream) {
		Board b = null;
		try {
			b = new Board();
			BufferedReader br = new BufferedReader(new InputStreamReader(
					istream));
			b.data = new int[NROW][];
			for (int m = 0, lenm = NROW; m < lenm; m++) {
				b.data[m] = new int[NCOL];
				for (int n = 0, lenn = NCOL; n < lenn; n++) {
					switch (br.read()) {
					case 'R':
						b.data[m][n] = 1;
						break;
					case 'G':
						b.data[m][n] = 2;
						break;
					case 'Y':
						b.data[m][n] = 3;
						break;
					case 'B':
						b.data[m][n] = 4;
						break;
					default:
						b.data[m][n] = -1;
						break;
					}
				}
				br.readLine();
			}
			br.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return b;
	}

	/**
	 * Plop a Bubble
	 * @param m Row
	 * @param n Column
	 * @throws Exception data[m][n] state must R/G/Y/B (1/2/3/4)
	 */
	public void plop(int m, int n) throws Exception {
		if (data[m][n] <= 0) throw new Exception("Error: [" + m + ", " + n + "] = " + data[m][n] + " (must >= 0)");

		Queue<Shot> qNextShot = new LinkedList<>();

		data[m][n]--;
		if (data[m][n] != 0)
			return;
		for (int c = 0; c < 500; c++) {
			Queue<Shot> qCurrent = qNextShot;
			qNextShot = new LinkedList<>();
			Queue<Shot> qPlop = new LinkedList<>();

			if (qCurrent.isEmpty() && c != 0)
				break;

			while (!qCurrent.isEmpty()) {
				Shot shot = qCurrent.poll();
				if (!shot.move())
					continue;

				if (data[shot.row][shot.col] > 0) {
					data[shot.row][shot.col]--;
					if (data[shot.row][shot.col] != 0)
						continue;
				}

				if (data[shot.row][shot.col] == 0)
					qPlop.add(shot);
				if (data[shot.row][shot.col] < 0)
					qNextShot.add(shot);
			}

			for (int i = 0; i < NROW; i++) {
				for (int j = 0; j < NCOL; j++) {
					if (data[i][j] == 0) {
						data[i][j] = -1;

						Shot newshot = new Shot(i, j, Direction.Up);
						if (newshot.isInsideBoard())
							qNextShot.add(newshot);

						newshot = new Shot(i, j, Direction.Right);
						if (newshot.isInsideBoard())
							qNextShot.add(newshot);

						newshot = new Shot(i, j, Direction.Down);
						if (newshot.isInsideBoard())
							qNextShot.add(newshot);

						newshot = new Shot(i, j, Direction.Left);
						if (newshot.isInsideBoard())
							qNextShot.add(newshot);

						int w = 0;
						Shot shot1 = null, shot2 = null;
						Iterator<Shot> iter = qPlop.iterator();
						while (iter.hasNext()) {
							Shot currShot = iter.next();
							if (currShot.row == i && currShot.col == j) {
								w++;
								if (w == 1)
									shot1 = currShot;
								else if (w == 2)
									shot2 = currShot;
							}
						}

						if (w > 1) {
							if (shot1.isVerticalShot()
									&& shot2.isHorizontalShot()) {
								qNextShot.add(shot1);
							} else if (shot1.isHorizontalShot()
									&& shot2.isVerticalShot()) {
								qNextShot.add(shot2);
							} else if (shot1.isHorizontalShot()
									&& shot2.isHorizontalShot()) {
								qNextShot.add(shot2);
							} else {
								qNextShot.add(shot2);
							}
							;
						}
					}
				}
			}
		}
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int m = 0; m < NROW; m++) {
			for (int n = 0; n < NCOL; n++) {
				switch (data[m][n]) {
				case 4:
					sb.append("| B ");
					break;
				case 3:
					sb.append("| Y ");
					break;
				case 2:
					sb.append("| G ");
					break;
				case 1:
					sb.append("| R ");
					break;
				case 0:
					sb.append("| X ");
					break;
				case -1:
					sb.append("| . ");
					break;
				}
			}
			sb.append("|\n");
		}
		return sb.toString();
	}

	@Override
	public boolean isSolution() {
		for (int m = 0; m < NROW; m++) {
			for (int n = 0; n < NCOL; n++) {
				if (data[m][n] > 0)
					return false;
			}
		}
		return true;
	}

	@Override
	public Collection<AbstractStep> getAllPossibleSteps() {
		ArrayList<AbstractStep> plops = new ArrayList<>();
		for (int m = 0; m < NROW; m++) {
			for (int n = 0; n < NCOL; n++) {
				if (data[m][n] > 0)
					plops.add(new Plop(m, n));
			}
		}
		return plops;
	}

	@Override
	public AbstractState createAppliedState(AbstractStep step) {
		if (step instanceof Plop) {
			try {
				Plop plop = (Plop) step;
				Board newboard = new Board(this);
				newboard.plop(plop.getRow(), plop.getCol());
				return newboard;
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		return null;
	}

	@Override
	public boolean equals(Object obj) {
		if (obj == null)
			return false;

		if (obj instanceof Board) {
			Board board = (Board) obj;
			for (int m = 0; m < NROW; m++) {
				for (int n = 0; n < NCOL; n++) {
					if (data[m][n] != board.data[m][n])
						return false;
				}
			}
			return true;
		} else {
			return false;
		}
	}
	
	/*
	public static void main(String args[]) {
		try {
			FileInputStream fis = new FileInputStream("level-01-037");
			Board board = Board.createBoard(fis);
			Board duplicate = new Board(board);
			System.out.println(board);
			
			long start = System.currentTimeMillis();
			Solver.BFS(board);
			// Solver.DLS(board, 6, new ArrayList<AbstractState>());
			// Solver.DLSIterative(board, 5);
			// Solver.DFS(board, new ArrayList<AbstractState>());
			long end = System.currentTimeMillis();
			Collection<AbstractStep> sols = board.getFirstSolutionSteps();
			System.out.println("Total Time: " + (end - start) + " milis");
			System.out.println("Total Move: " + sols.size());
			System.out.println();
			int i = 1;
			for (AbstractStep step : sols) {
				System.out.println(i++ + ". " + step);
				duplicate.plop(((Plop) step).getRow(), ((Plop) step).getCol());
				System.out.println(duplicate);
			}
		} catch (IOException ex) {
			ex.printStackTrace();
		} catch (Exception ex) {
			ex.printStackTrace();
		}
	}
	*/
}
